In a communications network, switching devices (“switches”) receive data at one of a set of input interfaces and forward the data to one or more of a set of output interfaces. Users typically require that such switching devices operate as quickly as possible in order to maintain a high data rate. Switches are typically data link layer devices that enable multiple physical network (e.g., local area network (LAN) and/or wide area network (WAN)) segments to be interconnected into a single larger network. In the most general sense, these types of networks transport data in the form of frames. A frame is a logical grouping of information sent as a unit over a transmission medium. Frames typically include header and/or trailer information used, for example, for routing, synchronization, and error control. The header and trailer information encapsulates payload data contained in the frame. The terms cell, datagram, message, packet and segment are also used to describe logical information groupings at various layers of the Reference Model for Open Systems Interconnect (OSI reference model) and in various terms of art. As used herein, the term “frame” should be understood in its broadest sense, and can encompass other terms such as cell, datagram, message, packet and segment.
FIG. 1 illustrates a simplified block diagram of a switching network 100, such as a LAN switching network. In this example, a switch 102 includes a switching medium 110 or “switch fabric” and multiple line cards 120 and 130. The switch connects various network devices 122, 124, 132, and 134 to each other through switching medium 110 via line cards 120 and 130. Network devices 122, 124, 132, and 134 can, in general, include a variety of different devices including computer systems, output devices, storage devices, communications devices, or other network components such as routers, other switches, and even other networks. For example, line cards 120 and 130 generally take the form of an I/O interface card that typically performs data frame analysis as part of the switching process. Switching medium 110 can be implemented in a variety of ways. Common types of switching mediums include single-bus architectures, shared-memory architectures, and crossbars.
It will be noted that the variable identifier “N” is used in FIG. 1 (and in other parts of this application) to more simply designate the final element (e.g., line card 130) of a series of related or similar elements. The repeated use of such variable identifiers is not meant to imply a correlation between the sizes of such series of elements, although such correlation may exist. The use of such variable identifiers does not require that each series of elements has the same number of elements as another series delimited by the same variable identifier. Rather, in each instance of use, the variable identified by “N” may hold the same or a different value than other instances of the same variable identifier.
FIG. 2 illustrates an exemplary network switching scheme. In support of a crossbar 200, switching medium 110 includes one or more input buffers 210 and one or more output buffers 220. In a typical implementation, there are input and output buffers for each port in the switching medium. Consequently, input and output buffers can be associated with particular line cards by virtue of the buffers' association with a particular port. In this example, data frames to be transferred from line card 120 to line card 130 are first queued in queue 240 of line card 120. Once a data frame is ready for transmission, it is serialized and transmitted across a serial channel to switching medium 110 where it is deserialized and received by input buffer 210. The data frame is then transmitted across crossbar 200 to an output buffer corresponding to the appropriate port of exit, in this case output buffer 220. From output buffer 220, the data frame is serialized and transmitted to the line card corresponding to output buffer 220 port, in this case line card 130. The data is typically deserialized and received in a queue such as queue 250.
Basic QoS support is attempted in a conventional system by prioritizing traffic classes independently at the ingress and the egress line cards of the switch. Specifically, packets are prioritized before their entry into the fabric port and then independently prioritized after transiting the fabric port on the egress side. There are at least two problems with this approach. First, high priority packets from one line card are treated no differently from low priority packets from another line card. So, the prioritization in effect is local to the ingress line cards and QoS is diluted from an overall system perspective. Second, fair allocation of bandwidth to each ingress line card is not assured at every egress line card such that one line card may effectively starve out another one.
Most fabrics deployed today are what are known as input-queued or input-output queued (hybrid) crossbars. These fabrics cannot service a packet from every ingress port in a single arbitration round, and therefore, require some packets to be buffered when multiple packets need to be serviced simultaneously. These types of crossbars are primarily used in practice due to scalability and cost-effectiveness reasons.
Another type of fabric is a pure output queued crossbar. This fabric is able to service all N fabric ports in a single arbitration round allowing it to buffer data only at its outputs. Thus, there is only a single point of congestion—the output queue, allowing scheduling to be performed solely at the egress queues. Here, packets can be prioritized and bandwidth may be fairly distributed in any desired manner. Unlike the input-queued/hybrid systems, the pure output queued crossbar is generally impractical to build.
It is increasingly desirable that switches support network administrative features, for example, quality of service (QoS) features such as fair bandwidth allocation between traffic classes and across fabric sources, prioritization and low latency queues, and other similar features. However, many primitive fabrics do not provide such support, and modifying the fabrics to include such support is not generally feasible. Accordingly, it is desirable to implement comprehensive QoS features over a primitive fabric system without having to modify the fabric itself.